package cn.com.mdx.sort.practice.collinearpoints;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p> 快速实现方式
 *
 * @author ：huangy
 * @date ：Created in 2020/9/16 5:10 下午
 */
public class FastCollinearPoints {
    /**
     * 点集合
     */
    private final Point[] points;

    public FastCollinearPoints(Point[] points) {
        if (!checkPoints(points)) throw new IllegalArgumentException("点集不符合要求");
        this.points = points;
    }

    /**
     * @return int
     * @Author huangy
     * @description //TODO 共线线段条数
     * @date 3:52 下午 2020/9/17
     **/
    public int numberOfSegments() {
        return segments().length;
    }

    /**
     * @return cn.com.mdx.sort.practice.collinearpoints.LineSegment[]
     * @Author huangy
     * @description //TODO 线段集合
     * @date 3:53 下午 2020/9/17
     **/
    public LineSegment[] segments() {
        //给点集排序
        List<LineSegment> lineSegmentList = new ArrayList<>();
        //数组拷贝
        Point[] copyPoints = Arrays.copyOf(points, points.length);
        for (Point base : points) {
            //基点
            //通过基点给拷贝数组排序
            Arrays.sort(copyPoints, base.slopeOrder());
            //线段端点
            Point min = base;
            Point max = base;
            //共线点计数，因为线段至少有两个端点，所以初始值为2
            int count = 2;
            for (int j = 0; j < copyPoints.length - 1; j++) {
                //计算相邻两点的斜率
                double s1 = base.slopeTo(copyPoints[j]);
                double s2 = base.slopeTo(copyPoints[j + 1]);
                if (s1 == s2) {
                    //相邻斜率相等，更新端点
                    if (max.compareTo(copyPoints[j + 1]) < 0) max = copyPoints[j + 1];
                    else if (min.compareTo(copyPoints[j + 1]) > 0) min = copyPoints[j + 1];
                    count++;
                    //如果达到点集末尾，则判断当前共线点数是否3个以上，且只添加基点为最小端点的线段
                    if (j + 1 == copyPoints.length - 1 && base.compareTo(min) == 0)
                        if (count > 3) lineSegmentList.add(new LineSegment(min, max));
                } else {
                    //判断共线点是否超过3，并只添加基点为最小端点的线段，去除重复线段的添加
                    /* 如下说明：
                     * 如果现在有5个共线点(1,1),(2,2),(3,3),(4,4),(5,5)
                     * 在基点是(1,1)时添加线段(1,1) -> (5,5)
                     * 在基点是(2,2)是不添加线段(2,2) -> (5,5)
                     * 因为线段(2,2) -> (5,5)是线段(1,1) -> (5,5)的子线段，避免重复添加
                     */
                    if (count > 3 && base.compareTo(min) == 0) lineSegmentList.add(new LineSegment(min, max));
                    count = 2;
                    //重置基点
                    /* 说明如下，将base与新斜率的第一个点进行比较
                     * 1.如果该点大于base 则说明该点在base的右上方位(包括上、右上、右)
                     * 则将min变为此点，max变为原来基点
                     * 2.如果该点小于base 则说明该点在base的左下方位(包括下、左下、左)
                     * 则将max变为此点，min变为原来的基点
                     * 这样能保证后面的点能正确的找到线段的左下端点和右上端点
                     */
                    if (base.compareTo(copyPoints[j + 1]) > 0) {
                        min = copyPoints[j + 1];
                        max = base;
                    } else {
                        min = base;
                        max = copyPoints[j + 1];
                    }
                }
            }
        }
        return lineSegmentList.toArray(new LineSegment[]{});
    }

    /**
     * @param points 被检测的点集
     * @return boolean false 不合法 true 合法
     * @Author huangy
     * @description //TODO 检测点集是否合法
     * @date 5:43 下午 2020/9/17
     **/
    private boolean checkPoints(Point[] points) {
        if (points == null || points.length < 4) return false;
        Arrays.sort(points);
        for (int i = 0; i < points.length - 1; i++) {
            if (points[i] == null) return false;
            if (points[i].compareTo(points[i + 1]) == 0) return false;
        }
        return true;
    }
}
